package assign2;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.Timer;
import java.util.TimerTask;
import java.util.TreeMap;
import java.util.TreeSet;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;

/**
 * Assignment 2 - Network.java
 * Contains all necessary functions to satify Assignment 2
 * requirements.
 *
 * @author Kelton Kowalchuk A00773813
 * @author Jitin Dhillon A00806890
 * 
 */
public class Network {
	    /**
	     * Keeps track of starting time.
	     */
		public static double startTime;
		/**
		 * Keeps track of ending time.
		 */
		public static double endTime;
		/**
		 * Print writer to write output.
		 */
		public static PrintWriter out;
		/**
		 * Timer class that will check if the program reaches 20 seconds, and exits.
		 */
		public class CheckTime extends TimerTask{

			@Override
			public void run() {
				endTime = System.nanoTime();
				if((endTime - startTime) / 1000000000 > 20){
					out.println(" No solution found.");
					out.flush();
					System.exit(1);
				}
			}
		}
	    
        public static void main(String[] args) {
                processTestCases(System.in, System.out);
        }
        /**
         * Method used to read in data and print out to specified streams.
         * @param input the input stream to read from.
         * @param output the output stream to print to.
         */
        public static void processTestCases(InputStream input, OutputStream output) {
                /**
                 * Creates a scanner object from the input stream.
                 */
                Scanner scan = new Scanner(input);
                /**
                 * Creates a PrintWriter object from the output stream.
                 */
                out = new PrintWriter(output);
                /**
                 * Get the start time.
                 */
                startTime = System.nanoTime();      
                /**
                 * Create timer for program
                 */
                Timer timer = new Timer();
                Network network = new Network();
                /**
                 * Schedule the timer to run every second.
                 */
                timer.schedule(network.new CheckTime() , 0, 1 * 1000);
                
                /**
                 * Stores the total number of test cases.
                 */
                int testTotal = scan.nextInt();
                /**
                 * Stores the number of labs in each case.
                 */
                int labCount;
                /**
                 * Stores the number of existing cables for each case.
                 */
                int existingCables;
                /**
                 * Map of coordinates.
                 */
                Map<Integer, int[]> coordinates = new HashMap<Integer, int[]>();
                /**
                 * Map of labs that are connected.
                 */
                Map<Integer, int[]> labsConnected = new HashMap<Integer, int[]>();
                /**
                 * 2D-array that holds the connected components (solution).
                 */
                int[][] solutionGraph;
                /**
                 * 2D-array that holds the distance between each lab.
                 */
                double[][] distanceGraph;
                /**
                 * 2D-array that is a copy of the distanceGraph (used for part 2)
                 */
                double[][] distanceGraphCopy;

                //Calculate the number of labs and existing cables.
                for (int i = 1; i <= testTotal; i++) {
                        //Print out the current test case number.
                        out.println("Test " + i);
                        //Read in the lab count for the current test case.
                        labCount = scan.nextInt();
                        //Read in the number of existing cables.
                        existingCables = scan.nextInt();
 
                        //Get the coordinates of each lab.
                        for (int j = 1; j <= labCount; j++) {
                                //Read in the x and y coordinates and store them in a temp int array
                                int[] tempCoords = { scan.nextInt(), scan.nextInt() };
                                //Store those in the coordinates map.
                                coordinates.put(j, tempCoords);
                        }
                                                
                        //Initialize distanceGraph and distanceGraphCopy to the size of labCount
                        distanceGraph = new double[labCount][labCount];
                        distanceGraphCopy = new double[labCount][labCount];
                        
                        //Calculate distance between each lab, and store in distanceGraph
                        for(int j = 1; j <= labCount; j++)
                            for(int k = 1; k <= labCount; k++) {
                                double distance = Math.sqrt(Math.pow((coordinates.get(k)[0] - coordinates.get(j)[0]), 2) 
                                        + Math.pow((coordinates.get(k)[1] - coordinates.get(j)[1]), 2));
                                distanceGraph[j-1][k-1] = (int)distance;
                            }
                        
                        //initialize distanceGraphCopy from distanceGraph
                        for(int j = 0; j < labCount; j++)
                            for(int k = 0; k < labCount; k++) {
                                distanceGraphCopy[j][k] = distanceGraph[j][k];
                            }
                        
                        //remove top half of distanceGraph matrix
                        for(int j = 0; j < labCount; j++)
                            for(int k = j; k < labCount; k++) {
                                distanceGraph[k][j] = 0;
                            }
                        
                        // Store each existing connection
                        for (int k = 1; k <= existingCables; k++) {
                                //Read in the starting and ending point of each cable, storing in a temp int array.
                                int[] tempConnections = { scan.nextInt(), scan.nextInt() };
                                //Store those in the labsConnected map.
                                labsConnected.put(k, tempConnections);
                        }
                        
                        //put the existing cables into solution matrix
                        solutionGraph = new int[labCount][labCount];
                        for(int k = 1; k <= existingCables; k++) {
                            int[] tempCoords = labsConnected.get(k);
                            solutionGraph[tempCoords[0] - 1][tempCoords[1] - 1] = 1;
                            solutionGraph[tempCoords[1] - 1][tempCoords[0] - 1] = 1;
                        }
                        
                        Set<Set<Integer>> allSets = new HashSet<Set<Integer>>();
                        
                        //Make a set for each lab.
                        for(int k = 0; k < labCount; k++) {
                            makeset(k, allSets);
                        }
                        
                        //Join the labs based on the existing cables into the same set.
                        for(int k = 1; k <= existingCables; k++) {
                            int[] tempLabs = labsConnected.get(k);
                            Set<Integer> s1 = find(tempLabs[0] - 1, allSets);
                            Set<Integer> s2 = find(tempLabs[1] - 1, allSets);
                            union(s1, s2, allSets);
                        }
                        
                        //Call Kruskal's algorithm.
                        algorithm(distanceGraph, solutionGraph, allSets);
                                               
                        
                        //Create an ArrayList to hold all the cables, and sort them
                        //with the smaller lab first.
                        ArrayList<int[]> allEdges = new ArrayList<int[]>();
                        for(int j = 0; j < labCount; j++)
                            for(int k = 0; k < labCount; k++) {
                                if(solutionGraph[j][k] == 1) {
                                    if(j > k) {
                                        int[] temp = {k+1, j+1};
                                        allEdges.add(temp);
                                    } else {
                                        int[] temp = {j+1, k+1};
                                        allEdges.add(temp);
                                    }
                                }
                            }
                        //Sort the edges based on alpha-numeric rules.
                        Collections.sort(allEdges, new CustomComparator());
                        
                        //Create and instantiate an TreeSet to store the cables for printing.
                        Set<String> finalEdges = new TreeSet<String>();
                        //Take values from allEdges, convert to strings in the correct format.
                        for(int n = 0; n < allEdges.size(); n++){
                        	String t = "";
                        	t = allEdges.get(n)[0] + " " + allEdges.get(n)[1];
                        	finalEdges.add(t);
                        }
                        
                        //Delete all the existing cables from the finalEdges.
                        for(int k = 1; k <= existingCables; k++) {
                            int[] intToString = labsConnected.get(k);
                            String toDelete = intToString[0] + " " + intToString[1];
                            String toDelete2 = intToString[1] + " " + intToString[0];
                            finalEdges.remove(toDelete);
                            finalEdges.remove(toDelete2);
                        }
                        
                        //Call WarshallFloyd's algorithm to find appropriate datacenter.
                        int dataCenter = WarshallFloyd(solutionGraph, distanceGraphCopy);
                        
                        //Print out the correct output.
                        printCollection(finalEdges, dataCenter, out);

                        out.println();
                }
                out.flush();
                System.exit(1);
        }
        /**
         * Function that uses a Kruskal approach to find the minimum distance between 2 labs.
         * @param d which will be the distanceGraph 2D array
         * @return coordinates of the minimum distance
         */
        public static int[] returnMinimumDistance(double[][] d) {
            //Initialize variable to use in for-loop
            int labs = d.length;
            //Variable to store the minimum distance, initialized to max value.
            double minDistance = Double.MAX_VALUE;
            //Initialize an array to return, will contain the 2 labs that the edge will connect.
            int[] returnArray = new int[2];
            //ArrayList to hold all the pairs of labs that have equal minimum distances
            ArrayList<int[]> equalLabDistances = new ArrayList<int[]>();
            //Go through distanceGraph and find the minimum value.
            for(int i = 0; i < labs; i++)
                for(int j = 0; j < labs; j++) {
                    if(d[i][j] == minDistance) {
                        if(i > j) {
                            int[] temp = {j, i};
                            equalLabDistances.add(temp);
                        } else {
                            int[] temp = {i, j};
                            equalLabDistances.add(temp);
                        }
                    }
                    if(d[i][j] != 0 && d[i][j] < minDistance) {
                        equalLabDistances.clear();
                        minDistance = d[i][j];
                        if(i > j) {
                            int[] temp = {j, i};
                            equalLabDistances.add(temp);
                        } else {
                            int[] temp = {i, j};
                            equalLabDistances.add(temp);
                        }
                    }
                    
                }
            Collections.sort(equalLabDistances, new CustomComparator());
            int[] tempArray = equalLabDistances.get(0);
            returnArray[0] = tempArray[0];
            returnArray[1] = tempArray[1];
            d[returnArray[0]][returnArray[1]] = 0;
            d[returnArray[1]][returnArray[0]] = 0;
            return returnArray;
        }
    	
        /**
         * Our implementation of Kruskal's algorithm
         * 
         * @param input the distanceGraph
         * @param solution the solutionGraph
         * @param allSets the set of all sets used to figure out if there's a cycle
         */
    	public static void algorithm(double[][] input, int[][] solution, Set<Set<Integer>> allSets) {            
    		while(!isEmpty(input)) {
    		    int[] tempDist = returnMinimumDistance(input);
    		    Set<Integer> s1 = find(tempDist[0], allSets);
    		    Set<Integer> s2 = find(tempDist[1], allSets);
    		    if(!s1.equals(s2)) {
    		        union(s1, s2, allSets);
    		        solution[tempDist[0]][tempDist[1]] = 1;
    		        solution[tempDist[1]][tempDist[0]] = 1;
    		    }
    		}
    	}
    	
    	/**
    	 *Prints the values of the parameter collection.
    	 */
    	public static void printCollection(Set<String> c, int d, PrintWriter out){
    	    if(c.isEmpty()) {
    	        out.println(" No new data cables required.");
    	    } else {
    	        for(String tmp : c){
    	            out.println(" " + tmp);
    	        }
    	    }
    	    out.println(" Data-centre: " + (d + 1));
    	}
    	
    	/**
    	 * Creates a set including the specifed integer value.
    	 * 
    	 * @param v the integer value.
    	 * @param s the set of all sets.
    	 * @return the set created.
    	 */
    	public static Set<Integer> makeset(int v, Set<Set<Integer>> s) {
    	    Set<Integer> temp = new HashSet<Integer>();
    	    temp.add(v);
    	    s.add(temp);
    	    return temp;   	    
    	}
    	
    	/**
    	 * Finds the set within allSets containing the specified integer.
    	 * 
    	 * @param x the integer to look for.
    	 * @param s the set of all sets to search in.
    	 * @return the set that contains x.
    	 */
    	public static Set<Integer> find(int x, Set<Set<Integer>> s) {
    	    for(Set<Integer> i : s) {
    	        if(i.contains(x)) {
    	            return i;
    	        }
    	    }
    	    Set<Integer> temp = new HashSet<Integer>();
    	    return temp;
    	}
    	
    	/**
    	 * Joins 2 sets together.
    	 *  
    	 * @param s1 first set.
    	 * @param s2 second set.
    	 * @param s3 set of all sets.
    	 */
    	public static void union(Set<Integer> s1, Set<Integer> s2, Set<Set<Integer>> s3) {
    	    s3.remove(s1);
    	    s3.remove(s2);
    	    s1.addAll(s2);
    	    s3.add(s1);
    	}
    	
    	/**
    	 * Checks to see all the distances have been removed from the distanceArray.
    	 * 
    	 * @param distanceArray the distanceGraph
    	 * @return if there are any values still inside.
    	 */
    	public static boolean isEmpty(double[][] distanceArray) {
    	    for(int i = 0; i < distanceArray.length; i++)
    	        for(int j = 0; j < distanceArray.length; j++) {
    	            if(distanceArray[i][j] != 0)
    	                return false;
    	        }
    	    return true;
    	}
    	
    	/**
    	 * Our implementation of Warshall/Floyd's algorithm.
    	 * 
    	 * @param solution the solutionGraph.
    	 * @param distance the distanceGraph.
    	 * @return datacenter.
    	 */
    	public static int WarshallFloyd(int[][] solution, double[][] distance) {
    	    for(int i = 0; i < solution.length; i++) {
    	        for(int j = 0; j < solution.length; j++) {
    	            if(i == j) {
    	                solution[j][i] = 0;
    	            } else if(solution[j][i] == 1) {
    	                
    	            } else
    	                solution[j][i] = solution.length;
    	        }
    	    }
    	    
    	    for(int k = 0; k < solution.length; k++) {
    	        for(int i = 0; i < solution.length; i++) {
    	            for(int j = 0; j < solution.length; j++) {
    	                int x = solution[i][k];
    	                int y = solution[k][j];
    	                if(!(x == solution.length || y == solution.length))
    	                    solution[i][j] = Math.min(solution[i][j], solution[i][k] + solution[k][j]);
    	            }
    	        }
    	    }
    	    
    	    ArrayList<Integer> maxValueForEachLab = new ArrayList<Integer>();
    	    
    	    for(int i = 0; i < solution.length; i++) {
    	        int max = -1;
    	        for(int j = 0; j < solution.length; j++) {
    	            if(solution[i][j] > max)
    	                max = solution[i][j];
    	        }
    	        maxValueForEachLab.add(i, max);
    	    }
    	    
    	    int min = Integer.MAX_VALUE;
    	    int datacenter = -1;
    	    for(int i = 0; i < maxValueForEachLab.size(); i++) {
    	        if(maxValueForEachLab.get(i) < min) {
    	             min = maxValueForEachLab.get(i);
    	             datacenter = i;
    	        }  
    	    }
    	    return datacenter;
    	}
    	
    	
}